今天就按照順序講我們的下一題(第五題)

題目

題目翻譯

給予一字串 s, 回傳在 s中可找到最長的回文子字串

解題步驟

以下是具體的解題步驟，使用 Markdown 語法書寫：

具體解題步驟：

1. 問題轉換
   利用動態規劃表 DP[i][j] 來表示字串 s[i..j] 是否是回文，最終目標是找到字串中最長的回文子串。

   • 若 DP[i][j] == true，則表示 s[i..j] 是回文子串。
   • 若 DP[i][j] == false，則 s[i..j] 不是回文子串。

2. 特殊情況處理

   • 若字串長度為 0 或 1，則該字串本身就是回文，直接返回該字串。

3. 初始化動態規劃表

   • 每個單一字符的子串必定是回文，因此將 DP[i][i] = true，代表所有單個字符的子串都是回文。
   • 檢查所有長度為 2 的子串，如果相鄰兩個字符相同，則這些長度為 2 的子串也是回文，將 DP[i][i+1] = true。

4. 遞迴檢查長度大於 2 的子串

   • 使用兩層迴圈來檢查長度大於 2 的子串。對於每個子串 s[i..j]，如果 s[i] == s[j] 且子串 s[i+1..j-1] 是回文（即 DP[i+1][j-1] == true），則可以確定 s[i..j] 是回文，更新 DP[i][j] = true。
   • 如果找到更長的回文子串，更新回文子串的起始位置 start 和最大長度 maxLen。

5. 更新結果

   • 每次發現新的、更長的回文子串時，更新記錄的起始位置和回文長度。這些資訊可以在最後用來提取最長的回文子串。

6. 返回結果

   • 最後，利用 s.substr(start, maxLen) 根據記錄的 start 和 maxLen 返回最長回文子串。這樣可以避免手動構建回文字串。

code

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        
        if (size <= 1) return s;

        // 動態規劃表初始化，DP[i][j] 表示 s[i..j] 是否是回文
        vector<vector<bool>> DP(size, vector<bool>(size, false));
        
        int maxLen = 1; // 最長回文子串的長度
        int start = 0;  // 最長回文子串的起始位置

        // 單個字符的子串一定是回文
        for (int i = 0; i < size; i++) {
            DP[i][i] = true;
        }

        // 檢查長度為2的子串是否是回文
        for (int i = 0; i < size - 1; i++) {
            if (s[i] == s[i + 1]) {
                DP[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }

        // 檢查長度大於2的子串
        for (int len = 3; len <= size; len++) {  // len 是子串的長度
            for (int i = 0; i <= size - len; i++) {
                int j = i + len - 1;  // j 是子串的結尾

                // 若 s[i] == s[j] 且中間的子串是回文，則 s[i..j] 是回文
                if (s[i] == s[j] && DP[i + 1][j - 1]) {
                    DP[i][j] = true;
                    if (len > maxLen) {
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }

        // 回傳最長回文子串
        return s.substr(start, maxLen);
    }
};